package 算法.排序算法;

import 算法.查找算法.基本查找;

public class 插入排序 {
    public static void main(String[] args) {
         /*
            插入排序：
                将0号索引的元素到N索引的元素看做是有序的，把N+1号索引的元素到最后一个当成是无序的。
                遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
                N的范围：0~最大索引
        */
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        //将3 44 看成是有序的后面看成是无需的

        //1.找到从记号索引开始是无须的（既不是递增的）。
        //定义变量记录开始无须的的索引
        int startIndex=-1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]>arr[i+1]){startIndex=i+1;break;}   //表示无需索引从这个索引开始
        }

        //2.开始插入排序
        //依次得到无需索引的每一个元素
        for (int i = startIndex; i < arr.length; i++) {
            //插入有序数组中：得到的每一个无需的元素，只需要对有序的元素进行比较
            //如果小于，则进行交换，一直左进行判断，直到遇到比它小的元素，后面的元素也是循环这个方法。

            //记录当前要插入的数据的索引
            int insertIndex=i;
            //插入的索引元素小于前一个索引元素则进行互换,一直重复,直到这个元素到遇到比自己更小的或者到最小.
            while (insertIndex>0&&arr[insertIndex]<arr[insertIndex-1]){
                //交换位置
                int tem=arr[insertIndex];
                arr[insertIndex]=arr[insertIndex-1];
                arr[insertIndex-1]=tem;
                insertIndex--;
            }

            //打印数组
            for (int j : arr) {
                System.out.print(j + " ");
            }
            System.out.println();
        }
    }
}
